/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        18.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/12 14:13
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，
//使得a + b + c + d的值与target相等？
//找出所有满足条件且不重复的四元组。
//
//注意：答案中不可以包含重复的四元组。
#include "../header.h"
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            vector<vector<int>> triples = threeSum(nums,i+1,target - nums[i]);
            for(auto &triple : triples){
                triple.push_back(nums[i]);
                ans.push_back(triple);
            }
            while (i < n - 1 && nums[i] == nums[i + 1])
                i++;
        }
        return ans;
    }
private:
    vector<vector<int>> threeSum(vector<int> &nums,int start, int target) {
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = start; i < n; ++i) {
            vector<vector<int>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
            for (auto &tuple:tuples) {
                tuple.push_back(nums[i]);
                ans.push_back(tuple);
            }
            while (i < n - 1 && nums[i] == nums[i + 1])
                i++;
        }
        return ans;
    }
    vector<vector<int>> twoSumTarget(const vector<int> &nums, int start, int target) {
        vector<vector<int>> ans;
        int lo = start, hi = nums.size() - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target)
                while (lo < hi && nums[lo] == left)
                    lo++;
            if (sum > target)
                while (lo < hi && nums[hi] == right)
                    hi--;
            if (sum == target) {
                ans.push_back({nums[lo], nums[hi]});
                while (lo < hi && nums[lo] == left)
                    lo++;
                while (lo < hi && nums[hi] == right)
                    hi--;
            }
        }
        return ans;
    }
};
